#include <stdio.h>
#include <string.h>
#include <stdlib.h>

// M
// int func(int h, int k)
// {
//     int f[20000] = {0};
//     f[0] = k + 1;
//     int t = f[0] + k + 1;
//     for (int i = 1; i <= h; i++)
//     {
//         f[i] = t;
//         t += f[i];
//     }
//     return f[h];
// }

// int main()
// {
//     int total = 0;
//     scanf("%d", &total);
//     int h = 0;
//     int k = 0;
//     for (int i = 0; i < total; ++i)
//     {
//         scanf("%d %d", &h, &k);
//         printf("%d\n", func(h, k));
//     }
//     return 0;
// }

// typedef struct Stu
// {
//     int _time;
//     int _price;
// } Stu;

// int compare(const void *a, const void *b)
// {
//     return ((Stu *)a)->_time - ((Stu *)b)->_time;
// }

// int main()
// {
//     int total = 0;
//     int num = 0;
//     scanf("%d", &total);
//     for (int i = 0; i < total; ++i)
//     {
//         scanf("%d", &num);
//         Stu *v = (Stu *)calloc(num, sizeof(Stu));
//         for (int j = 0; j < num; ++j)
//         {
//             scanf("%d %d", &v[j]._time, &v[j]._price);
//         }
//         qsort(v, num, sizeof(Stu), compare);
//         for (int j = 0; j < num; ++j)
//         {
//             printf("%d\n", v[j]._price);
//         }
//         free(v);
//     }
//     return 0;
// }

// K
// const char *key = "0123456789ABCDEF";
// void trans(int num, char *dest, int k)
// {
//     if (num == 0)
//     {
//         dest[0] = '0';
//         return;
//     }
//     int pos = 0;
//     while (num)
//     {
//         dest[pos++] = key[num % k];
//         num /= k;
//     }
//     // 反转
//     char *left = dest;
//     char *right = dest + pos - 1;
//     while (left < right)
//     {
//         char tmp = *left;
//         *left = *right;
//         *right = tmp;
//         ++left;
//         --right;
//     }
// }

// int main()
// {
//     int source = 0;
//     int k = 0;
//     while (scanf("%d %d", &source, &k) != EOF)
//     {
//         char result[33] = {0};
//         trans(abs(source), result, k);
//         if (source < 0)
//             printf("-");
//         printf("%s\n", result);
//     }
//     return 0;
// }

// J
// int main()
// {

//     // n n + 1 台电脑 1-n 操作n个回合
//     int n = 0;
//     char arr[101] = {0};
//     while (scanf("%d", &n) != EOF)
//     {
//         int result = 0;
//         for (int i = 2; i <= n; ++i)
//         {
//             for (int j = 1; i * j <= n; ++j)
//             {
//                 arr[i * j] = (arr[i * j] + 1) % 2;
//             }
//         }
//         for (int i = 1; i <= n; ++i)
//         {
//             if (arr[i] == 0)
//                 ++result;
//         }
//         printf("%d\n", result);
//     }

//     return 0;
// }

// I
// int compare(const void *a, const void *b)
// {
//     return abs(*(int *)b) - abs(*(int *)a);
// }

// int main()
// {
//     int nums[100] = {0};
//     int n = 0;
//     while (scanf("%d", &n) != EOF)
//     {
//         if (0 == n)
//             break;
//         for (int i = 0; i < n; ++i)
//             scanf("%d", nums + i);
//         qsort(nums, n, sizeof(int), compare);
//         for (int i = 0; i < n; ++i)
//             printf("%d ", nums[i]);
//         printf("\n");
//     }

//     return 0;
// }

// H
// int strcomp(char *s1, char *s2)
// {
//     if (s1 == s2)
//         return 0;
//     while (1)
//     {
//         if (*s1 == *s2 && *s1 == 0)
//         {
//             return 0;
//         }
//         if (*s1 != *s2)
//             return *s1 > *s2 ? 1 : -1;
//         ++s1;
//         ++s2;
//     }
// }
// int main()
// {
//     char a[81] = {0};
//     char b[81] = {0};
//     while (scanf("%s %s", a, b) != EOF)
//     {
//         printf("%d\n", strcomp(a, b));
//     }
//     return 0;
// }

// G  scanf("%[^\n]%*c", src); 代替 gets
// void mcopy(char *src, char *dst, int m)
// {
//     for (int i = 0; i + m - 1 < strlen(src); ++i)
//     {
//         dst[i] = src[i + m - 1];
//     }
// }

// int main()
// {

//     int n = 0;
//     while (scanf("%d", &n) != EOF)
//     {
//         char src[81] = {0};
//         char dest[81] = {0};
//         getchar();
//         scanf("%[^\n]%*c", src);
//         mcopy(src, dest, n);
//         printf("%s\n", dest);
//     }

//     return 0;
// }

// F
// int search(int list[], int n, int x)
// {
//     for (int i = 0; i < n; ++i)
//     {
//         if (list[i] == x)
//             return i;
//     }
//     return -1;
// }
// int main()
// {
//     int nums[10] = {0};
//     while (scanf("%d", nums) != EOF)
//     {
//         for (int i = 1; i < 10; ++i)
//             scanf("%d", nums + i);
//         int dest = 0;
//         scanf("%d", &dest);
//         int pos = search(nums, 10, dest);
//         if (pos > -1)
//             printf("%d\n", pos);
//         else
//             printf("Not found\n");
//     }

//     return 0;
// }

// E
// char mode = 0;
// int compare(const void *a, const void *b)
// {
//     return ((*(int *)a - *(int *)b) * (mode == 'A' ? 1 : -1));
// }

// int main()
// {
//     int nums[10] = {0};
//     while (scanf("%c", &mode) != EOF)
//     {
//         if (mode != 'A' && mode != 'D')
//         {
//             printf("%d\n", mode);
//             break;
//         }
//         for (int i = 0; i < 10; ++i)
//             scanf("%d", nums + i);
//         qsort(nums, 10, sizeof(int), compare);
//         for (int i = 0; i < 10; ++i)
//             printf("%d ", nums[i]);
//         printf("\n");
//         // 去掉 \n 影响
//         getchar();
//     }

//     return 0;
// }

// D
// void sumDiff(int op1, int op2, int *pSum, int *pDiff)
// {
//     *pSum = op1 + op2;
//     *pDiff = op1 - op2;
// }

// int main()
// {
//     int op1 = 0;
//     int op2 = 0;
//     while (scanf("%d %d", &op1, &op2) != EOF)
//     {
//         int result[2] = {0};
//         sumDiff(op1, op2, result, result + 1);
//         printf("sum=%d diff=%d\n", result[0], result[1]);
//     }
//     return 0;
// }

// C
// void sort(int *p, int n)
// {
//     for (int i = 0; i < n; ++i)
//     {
//         for (int j = 0; j < n - 1 - i; ++j)
//         {
//             if (p[j] > p[j + 1])
//             {
//                 int tmp = p[j];
//                 p[j] = p[j + 1];
//                 p[j + 1] = tmp;
//             }
//         }
//     }
// }

// int main()
// {
//     int n = 0;
//     int arr[100] = {0};
//     while (scanf("%d", &n) != EOF)
//     {
//         for (int i = 0; i < n; ++i)
//         {
//             scanf("%d", arr + i);
//         }
//         sort(arr, n);
//         for (int i = 0; i < n; ++i)
//         {
//             printf("%d ", arr[i]);
//         }
//         printf("\n");
//     }
//     return 0;
// }

// B
// // 这里不合理 应该是 const
// int length(char *s)
// {
//     int result = 0;
//     while (*s != 0)
//     {
//         ++result;
//         ++s;
//     }
//     return result;
// }

// int main()
// {
//     string s;
//     while (getline(cin, s))
//     {
//         cout << length(const_cast<char *>(s.c_str())) << endl;
//     }
//     return 0;
// }

// A
// int main()
// {
//     vector<string> v{"", "", ""};
//     while (cin >> v[0])
//     {
//         cin >> v[1];
//         cin >> v[2];
//         sort(v.begin(), v.end(), less<string>());
//         cout << v[0] << endl
//              << v[1] << endl
//              << v[2] << endl;
//     }
//     return 0;
// }